BZOJ3730 震波 <动态点分治>

Problem

震波

Description

在一片土地上有个城市，通过条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为，其中第i个城市的价值为。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理次操作：

表示发生了一次地震，震中城市为，影响范围为，所有与距离不超过的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
表示第个城市的价值变成了。

为了体现程序的在线性，操作中的都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为。

Input

第一行包含两个正整数和。
第二行包含个正整数，第个数表示。
接下来行，每行包含两个正整数，表示和之间有一条无向边。
接下来行，每行包含三个数，表示次操作。

Output

包含若干行，对于每个询问输出一行一个正整数表示答案。

Sample Input

8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

Sample Output

11100101

Hint

标签：动态点分治

Solution

终于学会动态点分辣QAQ~
赶快来肝几道基础题

先不考虑时间复杂度，那么对于每个操作显然可以暴力从震源向上爬统计答案。每次加上当前子树中距离符合题意的点，再减去其儿子（就是向上爬时此点的前驱）的子树中与其算重复的点。这样维护两个树状数组即可。
但是树高可以构造比大，这时就需要建立点分树，把树高降成。

提取重心建立点分树，对每个分治中心维护两个树状数组，第一个是其子树中到此分治中心的每种距离的所有点的点权和，第二个是其子树中到此分治中心的上一层分治中心的每种距离的所有点的点权和。
这样对于询问，每次向上爬，爬到每个分治中心统计；对于修改，每次向上爬，爬到每个分治中心更新树状数组即可。这样总复杂度是。

不过此题有些卡常，有三种策略：

用做
带fread大读优
将棵树状数组建到同一个大数组上，每个记录其起始指针和终止指针，可以避免vector的一些常数

Code

#include <bits/stdc++.h>
#define LOG 16
#define MAX_N 100000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, e, c[MAX_N+5], fa[MAX_N+5];
int w[MAX_N+5], sz[MAX_N+5], rt, tot;
int anc[MAX_N+5][LOG+1], dep[MAX_N+5];
int *p0[MAX_N+5], *p1[MAX_N+5], pr[MAX_N+5];
int BIT0[MAX_N*100], BIT1[MAX_N*100]; bool mrk[MAX_N+5];
struct node {int v, nxt;} E[(MAX_N<<1)+5];
void addedge(int u, int v) {E[e] = (node){v, pr[u]}, pr[u] = e++;}
void inc(int *tr, int p, int x, int l) {for (p = min(p+1, l); p <= l; p += (p&-p)) tr[p] += x;}
int sum(int *tr, int p, int l) {int ret = 0; for (p = min(p+1, l); p; p -= (p&-p)) ret += tr[p]; return ret;}
void init(int u) {
    for (int i = 1; i <= LOG; i++)
        anc[u][i] =anc[anc[u][i-1]][i-1];
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if ((v = E[i].v) ^ anc[u][0])
            anc[v][0] = u, dep[v] = dep[u]+1, init(v);
}
int LCA(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = LOG; ~i; i--)
        if (dep[a]-(1<<i) >= dep[b]) a = anc[a][i];
    if (a == b) return a;
    for (int i = LOG; ~i; i--) if (anc[a][i]^anc[b][i])
        a = anc[a][i], b = anc[b][i];
    return anc[a][0];
}
int dist(int u, int v) {return dep[u]+dep[v]-2*dep[LCA(u, v)];}
int getsz(int u, int f) {
    int ret = 1;
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if (((v = E[i].v) ^ f) && !mrk[v])
            ret += getsz(v, u);
    return ret;
}
void getrt(int u, int f) {
    sz[u] = 1, w[u] = 0;
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if (((v = E[i].v) ^ f) && !mrk[v])
            getrt(v, u), sz[u] += sz[v], w[u] = max(w[u], sz[v]);
    w[u] = max(w[u], tot-sz[u]); if (w[u] < w[rt]) rt = u;
}
void divide(int u, int f) {
    rt = 0, tot = getsz(u, 0), getrt(u, 0);
    fa[u = rt] = f, mrk[u] = true, sz[u] = tot+1;
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if (!mrk[v = E[i].v]) divide(v, u);
}
void modify(int x, int y) {
    inc(p0[x], 0, y, sz[x]);
    for (int u = x; fa[u]; u = fa[u]) {
        int dis = dist(fa[u], x);
        inc(p1[u], dis, y, sz[u]);
        inc(p0[fa[u]], dis, y, sz[fa[u]]);
    }
}
int query(int x, int y) {
    int ret = sum(p0[x], y, sz[x]);
    for (int u = x, dis; fa[u]; u = fa[u]) if ((dis = dist(fa[u], x)) <= y)
        ret += sum(p0[fa[u]], y-dis, sz[fa[u]])-sum(p1[u], y-dis, sz[u]);
    return ret;
}
int main() {
    read(n), read(m), w[0] = n;
    memset(pr, -1, sizeof pr);
    for (int i = 1; i <= n; i++) read(c[i]);
    for (int i = 1, u, v; i < n; i++)
        read(u), read(v), addedge(u, v), addedge(v, u);
    init(1), divide(1, 0); int cnt = 0, lst = 0;
    for (int i = 1; i <= n; cnt += sz[i++]+1)
        p0[i] = BIT0+cnt, p1[i] = BIT1+cnt;
    for (int i = 1; i <= n; i++) modify(i, c[i]);
    while (m--) {
        int opt, x, y; read(opt);
        read(x), read(y), x ^= lst, y ^= lst;
        if (opt) modify(x, y-c[x]), c[x] = y;
        else printf("%d\n", lst = query(x, y));
    }
    return 0;
}